﻿#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// show debug log
static bool isDebug = true;

// 打印数组
void printArray(int* ary, int start, int end) {
	if (end - start + 1 <= 0) {
		printf("[]\n");
		return;
	}
	// 字符串
	for (int i = start; i <= end; i++)
	{
		// 用数组‘,’形式分隔元素
		printf(i == start ? "[" : ",");
		printf("%d", ary[i]);
	}
	printf("]\n");
}

////////////////////////////////////////////////////////////////////// 递归法
// 辅助函数
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
	if (start >= end)
		return;
	// 求数组长度、中位数
	int len = end - start, mid = (len >> 1) + start;
	if (isDebug) {
		printf("\n数组长度%d，中位数%d\n", len, mid);
	}
	// 左半数组起止pos指针
	int left = start, end1 = mid;
	// 右半数组起止pos指针
	int right = mid + 1, end2 = end;
	if (isDebug) {
		printf("左数组：");
		printArray(arr, left, end1);
		printf("右数组：");
		printArray(arr, right, end2);
	}
	merge_sort_recursive(arr, reg, left, end1);
	merge_sort_recursive(arr, reg, right, end2);
	// 合并排序数组至reg
	int k = start;
	while (left <= end1 && right <= end2)
		reg[k++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
	// 合并左侧剩余的至reg
	while (left <= end1)
		reg[k++] = arr[left++];
	// 合并右侧剩余的至reg
	while (right <= end2)
		reg[k++] = arr[right++];
	// 拷贝排序后数组至arr
	for (k = start; k <= end; k++)
		arr[k] = reg[k];
	if (isDebug) {
		printf("排序后数组：\n");
		printArray(arr, start, end);
	}
}
// 递归, 自上而下的方法
void merge_sort1(int arr[], const int len) {
	// 开辟一个等长数组，辅助递归排序用
	int* reg = malloc(sizeof(int) * len);
	// 调用递归排序并合并方法
	merge_sort_recursive(arr, reg, 0, len - 1);
	free(reg);
}


/////////////////////////////////////////////////////// 迭代法
void merge_sort2(int arr[], int len) {
	// copy数组arr的头指针
	int* a = arr;
	// 开辟一个等长数组，辅助排序用
	int* b = (int*)malloc(len * sizeof(int));
	// 循环步长成倍增长
	for (int seg = 1; seg < len; seg += seg) {
		// 元素分组
		for (int start = 0; start < len; start += seg * 2) {
			// 组内划分数组
			int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
			if (isDebug) {
				printf("\n数组长度%d，起始位置%d，终止位置%d，中位数%d\n", high - low, low, high, mid);
			}
			int k = low;	// 记录分组的头指针
			int start1 = low, end1 = mid;
			int start2 = mid, end2 = high;
			if (isDebug) {
				printf("左数组：");
				printArray(arr, start1, end1 - 1);
				printf("右数组：");
				printArray(arr, start2, end2 - 1);
			}
			// 合并排序数组至b
			while (start1 < end1 && start2 < end2)
				b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
			// 合并左侧剩余的至b
			while (start1 < end1)
				b[k++] = a[start1++];
			// 合并右侧剩余的至b
			while (start2 < end2)
				b[k++] = a[start2++];
			if (isDebug) {
				printf("排序后数组：\n");
				printArray(arr, low, high - 1);
			}
		}
		// 交换ab指针
		int* temp = a;
		a = b;
		b = temp;
	}
	// 确保数据拷贝到arr数组
	if (a != arr) {
		int i;
		for (i = 0; i < len; i++)
			b[i] = a[i];
		b = a;
	}
	// 释放临时内存b
	free(b);
}

/// <summary>
///  测试用例
/// </summary>
/// <returns></returns>
int main() {
	int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
	const int len = (int)sizeof(arr) / sizeof(int);
	if (isDebug) {
		printf("\n数组长度%d，排序前数组：\n", len);
		printArray(arr, 0, len - 1);
	}
	merge_sort2(arr, len);
	if (isDebug) {
		printf("排序后数组：\n");
		printArray(arr, 0, len - 1);
	}
	return 0;
}